class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        
        int n=heightMap.size(),m=heightMap[0].size();
        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> q;
        vector<vector<bool>> vecFlg(n,vector<bool>(m));
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(i==0 || i==n-1 || j==0 || j==m-1){
                    q.push({heightMap[i][j],{i,j}});
                    vecFlg[i][j]=true;
                }
            }
        }
        int dx[4]={1,-1,0,0};
        int dy[4]={0,0,1,-1};
        int nRet=0;
        while(q.size()){
            int h=q.top().first;
            int x=q.top().second.first;
            int y=q.top().second.second;
            q.pop();
            for(int i=0;i<4;++i){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0 && nx<n && ny>=0 && ny<m && !vecFlg[nx][ny]){
                    vecFlg[nx][ny]=true;
                    if(heightMap[nx][ny]<h){
                        nRet+=h-heightMap[nx][ny];
                    }
                    q.push({max(h,heightMap[nx][ny]),{nx,ny}});
                }
            }
        }

        return nRet;
    }
};
